{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Unequal Adjacent Groups Subsequence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getWordsInLongestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长相邻不相等子序列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个下标从&nbsp;<strong>0</strong>&nbsp;开始的字符串数组&nbsp;<code>words</code>&nbsp;，和一个下标从&nbsp;<strong>0</strong>&nbsp;开始的数组&nbsp;<code>groups</code>&nbsp;，两个数组长度都是&nbsp;<code>n</code>&nbsp;。</p>\n",
    "\n",
    "<p>两个长度相等字符串的 <strong>汉明距离</strong>&nbsp;定义为对应位置字符&nbsp;<strong>不同</strong>&nbsp;的数目。</p>\n",
    "\n",
    "<p>你需要从下标&nbsp;<code>[0, 1, ..., n - 1]</code>&nbsp;中选出一个&nbsp;<strong>最长子序列</strong>&nbsp;，将这个子序列记作长度为 <code>k</code> 的&nbsp;<code>[i<sub>0</sub>, i<sub>1</sub>, ..., i<sub>k - 1</sub>]</code>&nbsp;，它需要满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>相邻</strong> 下标对应的 <code>groups</code> 值 <strong>不同</strong>。即，对于所有满足&nbsp;<code>0 &lt; j + 1 &lt; k</code>&nbsp;的&nbsp;<code>j</code>&nbsp;都有&nbsp;<code>groups[i<sub>j</sub>] != groups[i<sub>j + 1</sub>]</code>&nbsp;。</li>\n",
    "\t<li>对于所有&nbsp;<code>0 &lt; j + 1 &lt; k</code>&nbsp;的下标&nbsp;<code>j</code>&nbsp;，都满足&nbsp;<code>words[i<sub>j</sub>]</code> 和&nbsp;<code>words[i<sub>j + 1</sub>]</code>&nbsp;的长度 <strong>相等</strong>&nbsp;，且两个字符串之间的 <strong>汉明距离</strong>&nbsp;为 <code>1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个字符串数组，它是下标子序列&nbsp;<strong>依次</strong>&nbsp;对应&nbsp;<code>words</code>&nbsp;数组中的字符串连接形成的字符串数组。如果有多个答案，返回任意一个。</p>\n",
    "\n",
    "<p><strong>子序列</strong>&nbsp;指的是从原数组中删掉一些（也可能一个也不删掉）元素，剩余元素不改变相对位置得到的新的数组。</p>\n",
    "\n",
    "<p><b>注意：</b><code>words</code>&nbsp;中的字符串长度可能&nbsp;<strong>不相等</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, words = [\"bab\",\"dab\",\"cab\"], groups = [1,2,2]\n",
    "<b>输出：</b>[\"bab\",\"cab\"]\n",
    "<b>解释：</b>一个可行的子序列是 [0,2] 。\n",
    "- groups[0] != groups[2]\n",
    "- words[0].length == words[2].length 且它们之间的汉明距离为 1 。\n",
    "所以一个可行的答案是 [words[0],words[2]] = [\"bab\",\"cab\"] 。\n",
    "另一个可行的子序列是 [0,1] 。\n",
    "- groups[0] != groups[1]\n",
    "- words[0].length = words[1].length 且它们之间的汉明距离为 1 。\n",
    "所以另一个可行的答案是 [words[0],words[1]] = [\"bab\",\"dab\"] 。\n",
    "符合题意的最长子序列的长度为 2 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, words = [\"a\",\"b\",\"c\",\"d\"], groups = [1,2,3,4]\n",
    "<b>输出：</b>[\"a\",\"b\",\"c\",\"d\"]\n",
    "<b>解释：</b>我们选择子序列 [0,1,2,3] 。\n",
    "它同时满足两个条件。\n",
    "所以答案为 [words[0],words[1],words[2],words[3]] = [\"a\",\"b\",\"c\",\"d\"] 。\n",
    "它是所有下标子序列里最长且满足所有条件的。\n",
    "所以它是唯一的答案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == words.length == groups.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= groups[i] &lt;= n</code></li>\n",
    "\t<li><code>words</code>&nbsp;中的字符串&nbsp;<strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>words[i]</code> 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-unequal-adjacent-groups-subsequence-ii](https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-unequal-adjacent-groups-subsequence-ii](https://leetcode.cn/problems/longest-unequal-adjacent-groups-subsequence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[\"bab\",\"dab\",\"cab\"]\\n[1,2,2]', '4\\n[\"a\",\"b\",\"c\",\"d\"]\\n[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for i in range(n):\n",
    "            if groups[i] != pre:\n",
    "                ans.append(words[i])\n",
    "                pre = groups[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans_id = [0]\n",
    "        a = groups[0]\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != a:\n",
    "                ans_id.append(i)\n",
    "                a = groups[i]\n",
    "        return [words[idi] for idi in ans_id]\n",
    "        # def check(mid):\n",
    "        #     a = groups[0]\n",
    "        #     v = 1\n",
    "        #     for i in range(1, n):\n",
    "        #         if groups[i] != a:\n",
    "        #             a = groups[i]\n",
    "        #             v += 1\n",
    "\n",
    "        #     return\n",
    "        \n",
    "        # left = 0\n",
    "        # right = n\n",
    "        # while left <= right:\n",
    "        #     mid = (left + right) // 2\n",
    "        #     if check(mid):\n",
    "        #         left = mid + 1\n",
    "        #     else:\n",
    "        #         right = mid - 1\n",
    "        # return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != groups[i - 1]:\n",
    "                ans.append(words[i-1])\n",
    "        return ans + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            if groups[i] == groups[i - 1]:\n",
    "                del groups[i]\n",
    "                del words[i]\n",
    "                i -= 1\n",
    "                n -= 1\n",
    "            i += 1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        cur = -1\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if groups[i]!=cur:\n",
    "                cur = groups[i]\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def func(n,words,groups):\n",
    "            index =0 \n",
    "            index_list = [index]\n",
    "            result = []\n",
    "\n",
    "            for i in range(1,n):\n",
    "                if groups[i]!=groups[index]:\n",
    "                    index_list.append(i)\n",
    "                    index = i\n",
    "\n",
    "            for i in index_list:\n",
    "                result.append(words[i])\n",
    "\n",
    "            return result\n",
    "        \n",
    "        return func(n,words,groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, (x, y) in enumerate(pairwise(groups)):\n",
    "            if x != y:\n",
    "                ans.append(words[i])\n",
    "        ans.append(words[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # 前i个 上个取了1 能够取得的最大长度\n",
    "        ans = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            if groups[i] == groups[i-1]:\n",
    "                if len(words[i]) > len(ans[-1]):\n",
    "                    ans[-1] = words[i]\n",
    "            else: ans.append(words[i])\n",
    "        return ans\n",
    "                \n",
    "#         f = [[0,0,[]] for _ in range(n+1)]\n",
    "#         if groups[0] == 0:\n",
    "#             f[0][0] = -inf\n",
    "#         else: f[0][1] = -inf\n",
    "#         s = \"\"\n",
    "#         for i in range(n):\n",
    "#             f[i+1][1] = f[i][1]\n",
    "#             f[i+1][2] = f[i][2]\n",
    "#             if groups[i] == 1:\n",
    "#                 if f[i][0] + len(words[i]) > f[i][1]:\n",
    "#                     f[i+1][1] = f[i][0] + len(words[i])\n",
    "#                     f[i+1][2] = f[i][2] + [words[i]]\n",
    "#             f[i+1][0] = f[i][0]\n",
    "#             if groups[i] == 0:\n",
    "#                 if f[i][1] + len(words[i]) > f[i][0]:\n",
    "#                     f[i+1][0] = f[i][1] + len(words[i])\n",
    "#                     f[i+1][2] = f[i][2] + [words[i]]\n",
    "                    \n",
    "#         print(f)\n",
    "#         return f[n][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if i == 0 or groups[i] != groups[i - 1]:\n",
    "                res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        indexes = []\n",
    "        prev = ~groups[0]\n",
    "        for i, v in enumerate(groups):\n",
    "            if v != prev:\n",
    "                indexes.append(i)\n",
    "                prev = v\n",
    "        return [words[i] for i in indexes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        a=groups[0]\n",
    "        ans=[words[0]]\n",
    "        for i,v in enumerate(groups):\n",
    "            if v!=a:\n",
    "                a=v\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans=[words[0]]\n",
    "        flag=groups[0]\n",
    "        n=len(groups)\n",
    "        for i in range(n):\n",
    "            if groups[i]==1-flag:\n",
    "                ans+=[words[i]]\n",
    "                flag=1-flag\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        N = len(groups)\n",
    "        f = [ [ 0 ] * 2 for _ in range(N) ]\n",
    "        dp = [ [], [] ]\n",
    "        dp[groups[0]].append(words[0])\n",
    "        f[0][groups[0]] = 1\n",
    "        for j in range(1, N):\n",
    "            if f[j-1][1-groups[j]] + 1 > f[j-1][groups[j]]:\n",
    "                f[j][groups[j]] = f[j-1][1-groups[j]] + 1\n",
    "                dp[groups[j]] = dp[1-groups[j]] + words[j:j+1]\n",
    "            else:\n",
    "                f[j][groups[j]] = f[j-1][groups[j]]\n",
    "            f[j][1-groups[j]] = f[j-1][1-groups[j]]\n",
    "        # print(f, dp)\n",
    "        return dp[0] if f[N-1][0] > f[N-1][1] else dp[1]\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        cur = groups[0] ^ 1\n",
    "        for i, x in enumerate(groups):\n",
    "            if cur ^ x:\n",
    "                cur = x\n",
    "                res.append(words[i])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        before = 0\n",
    "        ans = [] \n",
    "        tmp = [] \n",
    "\n",
    "        for i in range(n):\n",
    "            before = groups[i]\n",
    "            tmp = [i]\n",
    "            for j in range(i+1, n):\n",
    "                if groups[j] != before:\n",
    "                    tmp.append(j)\n",
    "                    before = groups[j]\n",
    "            #print(tmp,ans)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "        \n",
    "        \n",
    "        result = [] * len(ans)\n",
    "        for i, c in enumerate(ans):\n",
    "            result.append(words[c])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        n = len(words)\n",
    "        flag = groups[0]\n",
    "        for i in range(n):\n",
    "            if groups[i] == flag:\n",
    "                res.append(words[i])\n",
    "                flag = 1 - flag\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        res = []\n",
    "        last = '0'\n",
    "        for i in range(n):\n",
    "            if groups[i]!=last:\n",
    "                res.append(words[i])\n",
    "                last = groups[i]\n",
    "        \n",
    "        res2 = []\n",
    "        last = '1'\n",
    "        for i in range(n):\n",
    "            if groups[i]!=last:\n",
    "                res2.append(words[i])\n",
    "                last = groups[i]\n",
    "        # print(res,res2)\n",
    "        return res if len(res)>len(res2) else res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        s=[0]\n",
    "        for i in range(1,len(groups)):\n",
    "            if groups[i]!=groups[s[-1]]:\n",
    "                s.append(i)\n",
    "        res=[0 for _ in range(0,len(s))]\n",
    "        for i in range(0,len(s)):\n",
    "            res[i]=words[s[i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        if n == 0:\n",
    "            return res\n",
    "        now = groups[0]\n",
    "        res.append(words[0])\n",
    "\n",
    "        for i in range(n):\n",
    "            if groups[i] != now:\n",
    "                now = groups[i]\n",
    "                res.append(words[i])\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        res = []\n",
    "        for i in range(n) :\n",
    "            if i and groups[i] == groups[i - 1] :\n",
    "                continue\n",
    "            res.append(words[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        for w, g in zip(words, groups):\n",
    "            if g!=pre:\n",
    "                ans.append(w)\n",
    "                pre = g\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        judge=100\n",
    "        index=[]\n",
    "        for i,x in enumerate(groups):\n",
    "            if x!=judge:\n",
    "                index.append(i)\n",
    "                judge=x\n",
    "        ans=[]\n",
    "        for i in index:\n",
    "            ans.append(words[i])\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        i = 1\n",
    "        while i < len(words):\n",
    "            if groups[i] == groups[i-1]:\n",
    "                del words[i]\n",
    "                del groups[i]\n",
    "                i -= 1\n",
    "            i += 1\n",
    "        return words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i == n - 1 or groups[i] != groups[i + 1]: ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        f = [0 for _ in range(n)]\n",
    "        fa = [-1 for _ in range(n)]\n",
    "        ans = ans_idx = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if f[i] < f[j] + 1:\n",
    "                        f[i] = f[j] + 1\n",
    "                        fa[i] = j\n",
    "            if ans <= f[i]:\n",
    "                ans_idx = i\n",
    "        res = []\n",
    "        while ans_idx >= 0:\n",
    "            res.insert(0, words[ans_idx])\n",
    "            ans_idx = fa[ans_idx]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        last = -1\n",
    "        res = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i]!=last:\n",
    "                res.append(words[i])\n",
    "            last = groups[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        loc = 0\n",
    "        while loc < n - 1:\n",
    "            if groups[loc] != groups[loc + 1]:\n",
    "                ans.append(words[loc])\n",
    "            loc +=1\n",
    "        ans.append(words[n - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        pre = -1\n",
    "        cnt = 0\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if groups[i] != pre:\n",
    "                ans.append(words[i])\n",
    "                pre = groups[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        before = 0\n",
    "        ans = [] \n",
    "        tmp = [] \n",
    "\n",
    "        for i in range(n):\n",
    "            before = groups[i]\n",
    "            tmp = [i]\n",
    "            for j in range(i+1, n):\n",
    "                if groups[j] != before:\n",
    "                    tmp.append(j)\n",
    "                    before = groups[j]\n",
    "            #print(tmp,ans)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp\n",
    "        \n",
    "        \n",
    "        result = [] * len(ans)\n",
    "        for i, c in enumerate(ans):\n",
    "            result.append(words[c])\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        clt, res = [], []\n",
    "        for i, group in enumerate(groups):\n",
    "            if len(clt) > 0 and clt[-1] == group:\n",
    "                continue\n",
    "            clt.append(group)\n",
    "            res.append(words[i])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if i == n - 1 or groups[i] != groups[i + 1]: ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        if n == 1:\n",
    "            return words\n",
    "        res = []\n",
    "        res.append(words[0])\n",
    "        for i in range(1, n):\n",
    "            if groups[i] != groups[i - 1]:\n",
    "                res.append(words[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [c for c,(x,y) in zip(words,pairwise(groups)) if x!=y] + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        len0, len1 = 0, 0\n",
    "        len0_idx, len1_idx = [], []\n",
    "        ans = 0\n",
    "        ans_idx = []\n",
    "        for i, bit in enumerate(groups):\n",
    "            if bit == 0:\n",
    "                if len1 + 1 > ans:\n",
    "                    len0_idx = len1_idx.copy()\n",
    "                    len0_idx.append(i)\n",
    "                    len0 = len1 + 1\n",
    "                    ans = len0\n",
    "                    ans_idx = len0_idx\n",
    "            elif bit == 1:\n",
    "                if len0 + 1 > ans:\n",
    "                    len1_idx = len0_idx.copy()\n",
    "                    len1_idx.append(i)\n",
    "                    len1 = len0 + 1\n",
    "                    ans = len1\n",
    "                    ans_idx = len1_idx\n",
    "        return list(map(lambda x: words[x], ans_idx))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        idx = 0\n",
    "        for g, it in groupby(groups):\n",
    "            if idx >= len(words): break\n",
    "            ans.append(words[idx])\n",
    "            idx += len(list(it))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        index=[]\n",
    "        index.append(0)\n",
    "        for i in range(1, len(groups)):\n",
    "            if groups[index[-1]]!=groups[i]:\n",
    "                index.append(i)\n",
    "\n",
    "        res = []\n",
    "        for i in index:\n",
    "            res.append(words[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans1,ans2 = [],[]\n",
    "        target = 1\n",
    "        for v,k in zip(words,groups):\n",
    "            if k == target:\n",
    "                ans1.append(v)\n",
    "                target= int(not target)\n",
    "        target = 0\n",
    "        for v,k in zip(words,groups):\n",
    "            if k == target:\n",
    "                ans2.append(v)\n",
    "                target=int(not target)\n",
    "        return ans1 if len(ans1) > len(ans2) else ans2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        cur = 1-groups[0]\n",
    "        for i in range(n):\n",
    "            if cur+groups[i]==1:\n",
    "                cur = 1-cur\n",
    "                ans.append(words[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        for (i, j) in pairwise(groups):\n",
    "            print(\"%d %d\" %(i, j))\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [w for (x, y), w in zip(pairwise(groups), words) if x != y] + [words[-1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        now = groups[0]\n",
    "        res = [words[0]]\n",
    "        for i in range(1,n):\n",
    "            if groups[i] != now:\n",
    "                res.append(words[i])\n",
    "                now = groups[i]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        def back(i,cur):\n",
    "            if i>=n:\n",
    "                return cur \n",
    "            j = i+1\n",
    "            while j<n and groups[j]==groups[j-1]:\n",
    "                j+=1\n",
    "            if j<n:\n",
    "                cur.append(j)\n",
    "            return back(j,cur)\n",
    "        \n",
    "\n",
    "        f= back(0,[0])\n",
    "        ans = []\n",
    "        for i in f:\n",
    "            ans.append(words[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "\n",
    "        candi = None\n",
    "        for i in range(n-1):\n",
    "            if i == 0 or groups[i+1] != groups[i]:\n",
    "                if candi and n-i-1 < len(candi): continue\n",
    "                t = [i]\n",
    "                for j in range(i+1, n):\n",
    "                    if groups[j] != groups[t[-1]]:\n",
    "                        t.append(j)\n",
    "                if candi is None or len(t)-1 > len(candi):\n",
    "                    candi = t[1:] if i else t\n",
    "\n",
    "        ans = [words[t] for t in candi] if candi else [words[0]]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        expect = 0\n",
    "        res1 = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i] == expect:\n",
    "                res1.append(words[i])\n",
    "                expect = 1 - expect\n",
    "        expect = 1\n",
    "        res2 = []\n",
    "        for i in range(len(groups)):\n",
    "            if groups[i] == expect:\n",
    "                res2.append(words[i])\n",
    "                expect = 1 - expect\n",
    "        return res1 if len(res1) >= len(res2) else res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        currentMaxLength = 0\n",
    "        answerIndexList = []\n",
    "        currentIndexList = []\n",
    "        currentGroupList = []\n",
    "        currentLength = 0\n",
    "        for i in range(n):\n",
    "            # try to add groups[i] into answerIndexList\n",
    "            if len(currentGroupList) == 0 or currentGroupList[-1] != groups[i]:\n",
    "                currentGroupList.append(groups[i])\n",
    "                currentIndexList.append(i)\n",
    "            else:\n",
    "                while len(currentGroupList)!=0 and currentGroupList[-1] == groups[i]:\n",
    "                    currentGroupList.pop(-1)\n",
    "                    currentIndexList.pop(-1)\n",
    "                currentGroupList.append(groups[i])\n",
    "                currentIndexList.append(i)\n",
    "            \n",
    "            # then we can process the length\n",
    "            currentLength = len(currentIndexList)\n",
    "            if currentLength > currentMaxLength:\n",
    "                currentMaxLength = currentLength\n",
    "                answerIndexList = copy.deepcopy(currentIndexList)\n",
    "                \n",
    "        return [words[index] for index in answerIndexList]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        return [words[i] for i, x in enumerate(groups) if i == 0 or x != groups[i - 1]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ls0,ls1 = [[0,-1]],[[1,-1]]\n",
    "        for i in range(n):\n",
    "            c = groups[i]\n",
    "            if c != ls0[-1][1]:\n",
    "                ls0.append([i,c])\n",
    "            if c != ls1[-1][1]:\n",
    "                ls1.append([i,c])\n",
    "        \n",
    "        print(ls0,ls1)\n",
    "        ans = []\n",
    "        if len(ls0) > len(ls1):\n",
    "            ls0.pop(0)\n",
    "            for index,_ in ls0:\n",
    "                ans.append(words[index])\n",
    "        else:\n",
    "            ls1.pop(0)\n",
    "            for index,_ in ls1:\n",
    "                ans.append(words[index])\n",
    "\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "                \n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # 定义f[i + 1] 表示以i为结尾的子序列所能取得的最大值\n",
    "        # j从0到i-1枚举\n",
    "        # 如果words[j]和words[i]的距离是1，且len(words[j]) == len(words[i]) 且groups[j] !=groups[i]\n",
    "        # 去长度最大值\n",
    "        def hdist1(a: str, b: str) -> int:\n",
    "            res = 0\n",
    "            for a1, b1 in zip(a, b):\n",
    "                if a1 != b1:\n",
    "                    res += 1\n",
    "                    if res > 1:\n",
    "                        return False\n",
    "            return res == 1\n",
    "        f = [[] for _ in range(n + 1)]\n",
    "        ans = []\n",
    "        for i, (w, g) in enumerate(zip(words, groups)):\n",
    "            f[i + 1].append(w)\n",
    "            for j in range(i):\n",
    "                if groups[j] != g:\n",
    "                    if len(f[j + 1]) + 1 > len(f[i + 1]):\n",
    "                        f[i + 1] = f[j + 1] + [w]\n",
    "            if len(f[i + 1]) > len(ans):\n",
    "                ans = f[i + 1]\n",
    "        return ans\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        maxlen = [0 for _ in range(n)]\n",
    "        wordss = [[] for _ in range(n)]\n",
    "        maxlen[0] = 1\n",
    "        wordss[0] = [words[0]]\n",
    "        for i in range(1, n):\n",
    "            cur = -1\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j] and maxlen[j] > maxlen[i]:\n",
    "                    maxlen[i] = maxlen[j]\n",
    "                    cur = j\n",
    "            if cur != -1:\n",
    "                wordss[i] = copy.deepcopy(wordss[cur])\n",
    "            maxlen[i] += 1\n",
    "            wordss[i].append(words[i])\n",
    "        maxx = 0\n",
    "        pos = 0\n",
    "        for i in range(n):\n",
    "            if maxlen[i] > maxx:\n",
    "                maxx = maxlen[i]\n",
    "                pos = i\n",
    "        return wordss[pos]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        max_len = [[0,0] for _ in range(n)]\n",
    "        sol = [[[],[]] for _ in range(n)]\n",
    "        \n",
    "        max_len[0][0] = 0\n",
    "        max_len[0][1] = 1\n",
    "        sol[0][1] = [0]\n",
    "        \n",
    "        def satisfy(s1, s2):\n",
    "            if len(s1) != len(s2):\n",
    "                return False\n",
    "            diff = False\n",
    "            for a,b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    if not diff:\n",
    "                        diff = True\n",
    "                    else:\n",
    "                        return False\n",
    "            if not diff:\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        for s in range(1, n):\n",
    "            find = []\n",
    "            for further in range(s-1, -1, -1):\n",
    "                if groups[further] != groups[s]:\n",
    "                    find.append(further)\n",
    "            max_len[s][0], tag = max([max_len[s-1][0], 0], [max_len[s-1][1], 1])\n",
    "            if not tag:\n",
    "                sol[s][0] = sol[s-1][0]\n",
    "            else:\n",
    "                sol[s][0] = sol[s-1][1]\n",
    "\n",
    "            if not find:\n",
    "                max_len[s][1] = 1\n",
    "                sol[s][1] = [s]\n",
    "            else:\n",
    "                max_len[s][1], maxf = max([(max_len[f][1] + 1,f) for f in find])\n",
    "                sol[s][1] = sol[maxf][1] + [s]\n",
    "        \n",
    "        _, tag = max((max_len[n-1][0], 0), (max_len[n-1][1], 1))\n",
    "        if tag:\n",
    "            return [words[i] for i in sol[n-1][1]]\n",
    "        else:\n",
    "            return [words[i] for i in sol[n-1][0]]\n",
    "\n",
    "# print(Solution().getWordsInLongestSubsequence(3, [\"bab\",\"dab\",\"cab\"], [1,2,2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getWordsInLongestSubsequence(self, n, words, groups):\n",
    "\n",
    "        def get_dist(i, j):\n",
    "            return 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                return []\n",
    "\n",
    "            ans = []\n",
    "            for j in range(i + 1, n):\n",
    "                if groups[i] == groups[j]:\n",
    "                    continue\n",
    "                if get_dist(i, j) != 1:\n",
    "                    continue\n",
    "                result = dfs(j)\n",
    "                ans = max(ans, result, key=lambda x: len(x))\n",
    "            return [i] + ans\n",
    "\n",
    "        indices = dfs(0)\n",
    "        results = []\n",
    "        for index in indices:\n",
    "            results += [words[index]]\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        \n",
    "        stat = [[False]*n for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            for j in range(0, i):\n",
    "                if groups[i]!=groups[j]:\n",
    "                    stat[i][j] = True\n",
    "        \n",
    "        dp = [1]*n\n",
    "        indexs = [[0]]\n",
    "        res = 0\n",
    "        max_len = 1\n",
    "        for i in range(1, n):\n",
    "            tmp_index = -1\n",
    "            cnt = 0\n",
    "            for j in range(0, i):\n",
    "                if stat[i][j]:\n",
    "                    if dp[j] > cnt:\n",
    "                        cnt = dp[j]\n",
    "                        tmp_index = j\n",
    "            if tmp_index != -1:\n",
    "                indexs.append(indexs[tmp_index]+[i])\n",
    "                dp[i] = cnt+1\n",
    "            else:\n",
    "                indexs.append([i])\n",
    "            if len(indexs[-1])> max_len:\n",
    "                max_len = len(indexs[-1])\n",
    "                res = i\n",
    "        return [words[x] for x in indexs[res]]\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = [0]\n",
    "        def dfs(index):\n",
    "            for i in range(index+1,n):\n",
    "                if groups[i] != groups[index]:\n",
    "                    ans.append(i)\n",
    "                    dfs(i)\n",
    "                    return\n",
    "        dfs(0)\n",
    "        re = list(map(lambda x:words[x],ans))\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        dp=[[i] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if groups[j]!=groups[i]:\n",
    "                    dp[j]=max(dp[j],dp[i]+[j],key=len)\n",
    "\n",
    "        arr=max(dp,key=len)\n",
    "        return [words[u] for i,u in enumerate(arr)]\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(\n",
    "        self, n: int, words: List[str], groups: List[int]\n",
    "    ) -> List[str]:\n",
    "        # dp[i] 表示以 words[i] 结尾的最长子序列长度\n",
    "        dp = [1] * n\n",
    "        pre = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if dp[j] + 1 > dp[i]:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        pre[i] = j\n",
    "\n",
    "        maxLen = max(dp)\n",
    "        maxIndex = dp.index(maxLen)\n",
    "        res = []\n",
    "        while maxIndex != -1:\n",
    "            res.append(words[maxIndex])\n",
    "            maxIndex = pre[maxIndex]\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    exit()\n",
    "\n",
    "\n",
    "# --idea\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/15 16:19\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str],\n",
    "                                     groups: List[int]) -> List[str]:\n",
    "        nums = [0]\n",
    "        for v in range(1, n):\n",
    "            if groups[v] != groups[nums[-1]]:\n",
    "                nums.append(v)\n",
    "        return [words[i] for i in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        pref = list(range(n))\n",
    "        def ham(s, t):\n",
    "            if len(s) != len(t):\n",
    "                return False\n",
    "            dis = 0\n",
    "            for i in range(len(s)):\n",
    "                if s[i] != t[i]:\n",
    "                    dis += 1\n",
    "            return dis == 1\n",
    "    \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            r = 1\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j]:\n",
    "                    if 1 + dfs(j) > r:\n",
    "                        pref[i] = j\n",
    "                        r = 1 + dfs(j)\n",
    "            return r\n",
    "        \n",
    "        m = 1\n",
    "        mi = 0\n",
    "        for i in range(n):\n",
    "            k = dfs(i)\n",
    "            if m < k:\n",
    "                m = k\n",
    "                mi = i\n",
    "        l = []\n",
    "        while pref[mi] != mi:\n",
    "            l.append(words[mi])\n",
    "            mi = pref[mi]\n",
    "        l.append(words[mi])\n",
    "        l.reverse()\n",
    "        dfs.cache_clear()\n",
    "        return l\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, w: List[str], g: List[int]) -> List[str]:\n",
    "        \n",
    "        def f(i, pre, path):\n",
    "            if i == n: return\n",
    "            if g[i] == pre:\n",
    "                f(i + 1, pre, path)\n",
    "                return\n",
    "            path.append(w[i])\n",
    "            f(i + 1, g[i], path)\n",
    "        \n",
    "        ans1, ans2 = [], []\n",
    "        \n",
    "        f(0, 0, ans1)\n",
    "        f(0, 1, ans2)\n",
    "        \n",
    "        if len(ans1) >= len(ans2):\n",
    "            return ans1\n",
    "        else:\n",
    "            return ans2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')\n",
    "INFMAX = float('inf')\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "\n",
    "def input():\n",
    "    return sys.stdin.readline().rstrip()\n",
    "\n",
    "\n",
    "def end(r=-1):\n",
    "    print(r)\n",
    "    exit()\n",
    "\n",
    "\n",
    "# --idea\n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/15 16:23\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str],\n",
    "                                     groups: List[int]) -> List[str]:\n",
    "        def ok(s, t):\n",
    "            return len(s) == len(t) and sum(x != y for x, y in zip(s, t)) == 1\n",
    "\n",
    "        f = [1] * n\n",
    "        pre = [-1] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if f[j] >= f[i] and groups[j] != groups[i]:\n",
    "                    f[i] = f[j] + 1\n",
    "                    pre[i] = j\n",
    "\n",
    "        i = f.index(max(f))\n",
    "        ans = []\n",
    "        while i != -1:\n",
    "            ans.append(i)\n",
    "            i = pre[i]\n",
    "        return [words[i] for i in reversed(ans)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        maxr=[]\n",
    "        d=dict()\n",
    "        def f(pos):\n",
    "            if pos in d:return d[pos].copy()\n",
    "            if pos==len(groups)-1:\n",
    "                return [pos]\n",
    "            if groups[pos]!=groups[pos+1]:\n",
    "                maxr=[pos]\n",
    "            else:\n",
    "                return []\n",
    "            maxr2=[]\n",
    "            for p2 in range(pos+1,len(words)):\n",
    "                r=f(p2)\n",
    "                if len(r)>len(maxr2):\n",
    "                    maxr2=r\n",
    "            d[pos]=maxr+maxr2\n",
    "            return d[pos]\n",
    "\n",
    "\n",
    "        for pos in range(len(groups)):\n",
    "            r=f(pos)\n",
    "            if len(r)>len(maxr):\n",
    "                maxr=r\n",
    "        a=[]\n",
    "        for e in maxr:\n",
    "            a.append(words[e])\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def ham(s1, s2):\n",
    "            f = 0\n",
    "            if len(s1) != len(s2): return False\n",
    "            for x, y in zip(s1, s2):\n",
    "                if x != y: f += 1\n",
    "                if f > 1: break\n",
    "            return f == 1\n",
    "\n",
    "        # dp = [-1] * n\n",
    "        # path = [-1] * n\n",
    "\n",
    "        dp = [[-1, -1] for _ in range(n)]\n",
    "        cur = 0\n",
    "        for i, x in enumerate(words):\n",
    "            tt = -1\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j] and ham(x, words[j]):\n",
    "                    tt = j if tt == -1 or dp[j][0] > dp[tt][0] else tt\n",
    "            dp[i] = [dp[tt][0] + 1 if tt != -1 else 1, tt]\n",
    "            # path[i] = tt\n",
    "            cur = i if dp[i][0] > dp[cur][0] else cur\n",
    "        res = []\n",
    "        while cur != -1:\n",
    "            res.append(words[cur])\n",
    "            cur = dp[cur][1]\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        dp = [[] for _ in range(n + 1)]\n",
    "        ans = []\n",
    "\n",
    "        def dis(s1, s2):\n",
    "            ret = 0\n",
    "            for c1, c2 in zip(s1, s2):\n",
    "                ret += int(c1 != c2)\n",
    "            return ret + abs(len(s1) - len(s2))\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            dp[i] = [word]\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if len(word) == len(words[j]) and dis(word, words[j]) == 1 and groups[i] != groups[j]:\n",
    "                    if len(dp[i]) < len(dp[j]) + 1:\n",
    "                        dp[i] = dp[j] + [word]\n",
    "            if len(dp[i]) > len(ans):\n",
    "                ans = dp[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def ham(s1,s2):\n",
    "            f = 0\n",
    "            if len(s1)!=len(s2):return False\n",
    "            for x,y in zip(s1,s2):\n",
    "                if x!=y:f+=1\n",
    "                # if f>1:break\n",
    "            return f==1\n",
    "\n",
    "        dp = [[] for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i,x in enumerate(words):\n",
    "            tt = -1\n",
    "            for j in range(i):\n",
    "                if groups[j]!=groups[i] and ham(words[j], words[i]):\n",
    "                    tt = j if tt==-1 or len(dp[j])>len(dp[tt]) else tt\n",
    "            dp[i] = dp[tt]+[i] if tt!=-1 else [i]\n",
    "            ans = i if len(dp[i])>len(dp[ans]) else ans\n",
    "        return [words[i] for i in dp[ans]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def isvalid(words,groups,a, b):\n",
    "            if len(words[a]) != len(words[b]): return False\n",
    "            if groups[a]==groups[b]:return False\n",
    "            k = 0\n",
    "            for i in range(len(words[a])):\n",
    "                if words[a][i] != words[b][i]:\n",
    "                    k += 1\n",
    "            return k == 1\n",
    "        dp = [[] for _ in range(n)]\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if isvalid(words,groups,i,j):\n",
    "                    if len(dp[i])<len(dp[j]):\n",
    "                        dp[i] = dp[j][:]\n",
    "            dp[i].append(words[i])\n",
    "            if len(dp[i])>len(res):\n",
    "                res = dp[i]\n",
    "        return res\n",
    "                        \n",
    "        \n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def f(i,j):\n",
    "            if groups[i] == groups[j]:\n",
    "                return False\n",
    "            x,y = words[i], words[j]\n",
    "            c = 0\n",
    "            if len(x) != len(y):\n",
    "                return False\n",
    "            for i in range(len(x)):\n",
    "                if x[i] != y[i]:\n",
    "                    c += 1\n",
    "                if c > 1:\n",
    "                    return False\n",
    "            return c == 1\n",
    "        cache = dict()\n",
    "        def g(i):\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "            if i == len(words)-1:\n",
    "                return [words[i],]\n",
    "            ans = []\n",
    "            for j in range(i+1, len(words)):\n",
    "                if f(i,j):\n",
    "                    t = g(j)\n",
    "                    if len(t) > len(ans):\n",
    "                        ans = t\n",
    "            cache[i] = [words[i]] + ans\n",
    "            return cache[i]\n",
    "        ans = []\n",
    "        for i in range(len(words)):\n",
    "            t = g(i)\n",
    "            if len(t) > len(ans):\n",
    "                ans = t\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def getC(s1, s2):\n",
    "            if len(s1) != len(s2): return inf\n",
    "            count = 0\n",
    "            for index in range(len(s1)):\n",
    "                if s1[index] != s2[index]:\n",
    "                    count += 1\n",
    "                if count > 1: return inf\n",
    "            return inf if not count else 1\n",
    "\n",
    "        indexed = defaultdict(set)\n",
    "        for index, item in enumerate(groups):\n",
    "            indexed[item].add(index)\n",
    "\n",
    "        @cache \n",
    "        def dp(i):\n",
    "            if i < 0: return ''\n",
    "            r = []\n",
    "            for pre in range(n):\n",
    "                if pre >= i: break\n",
    "                if pre in indexed[groups[i]] or (getC(words[i], words[pre]) != 1): continue\n",
    "                if len(dp(pre)) > len(r): r = dp(pre)\n",
    "            return list(r) + [words[i]]\n",
    "\n",
    "        res = []\n",
    "        for index in range(n):\n",
    "            t = dp(index)\n",
    "            if len(t) > len(res):\n",
    "                res = t\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        ans = []\n",
    "        N = len(groups)\n",
    "        # 汉明距离\n",
    "        H = [ [ 0 ] * N for _ in range(N) ]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if len(words[i]) == len(words[j]):\n",
    "                    H[i][j] = sum(c1 != c2 for c1, c2 in zip(words[i], words[j])) if i != j else 0\n",
    "                    H[j][i] = H[i][j]\n",
    "                else:\n",
    "                    H[i][j] = H[j][i] = -1\n",
    "        \n",
    "        dp = [ [] * N for _ in range(N) ]\n",
    "        \n",
    "        for i in range(N):\n",
    "            dp[i] = words[i:i+1]\n",
    "            for j in range(i):\n",
    "                if groups[i] != groups[j] and H[i][j] == 1 and len(dp[i]) < len(dp[j]) + 1:\n",
    "                    dp[i] = dp[j] + words[i:i+1]\n",
    "        # print(H, dp)\n",
    "        ans = 0\n",
    "        ret = []\n",
    "        for i in range(N):\n",
    "            if len(dp[i]) > ans:\n",
    "                ans = len(dp[i])\n",
    "                ret = dp[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# auther yeling\n",
    "from typing import List\n",
    "from bisect import *\n",
    "from collections import *\n",
    "from functools import *\n",
    "from itertools import *\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import Optional\n",
    "from heapq import *\n",
    "import string\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "INF = 2 ** 64 - 1\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:    \n",
    "        vis = [[False] * n for _ in range(n)]\n",
    "        dp = [[] for _ in range(n)]\n",
    "        def isVis(a, b):\n",
    "            if len(a) != len(b):\n",
    "                return False\n",
    "            diff = 0\n",
    "            for x,y in zip(a,b):\n",
    "                if x != y:\n",
    "                    diff += 1\n",
    "                    if diff > 1:\n",
    "                        return False\n",
    "            return True\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            temp = []\n",
    "            for j in range(0, i):\n",
    "                if isVis(words[i], words[j]) and groups[i] != groups[j]:\n",
    "                    if len(dp[j]) > len(temp):\n",
    "                        temp = dp[j][:]\n",
    "            temp.append(i)\n",
    "            dp[i] = temp\n",
    "            if len(temp) > len(ans):\n",
    "                ans = temp[:]\n",
    "            # print(dp)\n",
    "        ret = []\n",
    "        for v in ans:\n",
    "            ret.append(words[v])\n",
    "\n",
    "        return ret\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        \n",
    "        def check(a,b):\n",
    "            if len(a)!=len(b):return False\n",
    "            cnt=0\n",
    "            for u,v in zip(a,b):\n",
    "                if u!=v:cnt+=1\n",
    "                if cnt>1:return False\n",
    "            return cnt==1\n",
    "        \n",
    "        n=len(words)\n",
    "        dp=[[words[i]] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if groups[i]!=groups[j] and check(words[i],words[j]):\n",
    "                    if len(dp[i])<len(dp[j])+1:\n",
    "                        dp[i]=dp[j]+[words[i]]\n",
    "        \n",
    "        print(dp)\n",
    "        mx=0\n",
    "        for i in range(n):\n",
    "            mx=max(mx,len(dp[i]))\n",
    "        for i in range(n):\n",
    "            if len(dp[i])==mx:\n",
    "                return dp[i]\n",
    "        return dp[-1]\n",
    "                    \n",
    "                \n",
    "                \n",
    "                    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        dup_map = [ [False] * n for _ in range(n)]\n",
    "        \n",
    "        for i in range(n) :\n",
    "            for j in range(i+1, n) :\n",
    "                if len(words[i]) != len(words[j]) :\n",
    "                    dup_map[i][j] = False\n",
    "                else :\n",
    "                    cnt = 0\n",
    "                    for k in range(len(words[i])) :\n",
    "                        if words[i][k] != words[j][k] :\n",
    "                            cnt += 1\n",
    "                    if cnt == 1 :\n",
    "                        dup_map[i][j] = True\n",
    "                    else :\n",
    "                        dup_map[i][j] = False\n",
    "                        \n",
    "        @cache\n",
    "        def dfs(i) :\n",
    "            if i == n :\n",
    "                return []\n",
    "            \n",
    "            tmp = []\n",
    "            for j in range(i+1, n) :\n",
    "                if groups[i] != groups[j] and dup_map[i][j]:\n",
    "                    k = dfs(j).copy()\n",
    "                    k.append(words[j])\n",
    "                    if len(k) > len(tmp) :\n",
    "                        tmp = k\n",
    "            # k2 = dfs(i+1).copy()\n",
    "            # if len(k2) > len(tmp) :\n",
    "            #     tmp = k2\n",
    "            return tmp\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n) :\n",
    "            k = dfs(i).copy()\n",
    "            k.append(words[i])\n",
    "            if len(k) > len(ans) :\n",
    "                ans = k\n",
    "        ans.reverse()\n",
    "        \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        \n",
    "        n = len(words)\n",
    "        \n",
    "        dis = [[0]*n for i in range(n)]\n",
    "        def getdis(a,b):\n",
    "            a = list(a)\n",
    "            b = list(b)\n",
    "            re = 0\n",
    "            if len(a) != len(b):\n",
    "                return 100\n",
    "            for pa,pb in zip(a,b):\n",
    "                if pa != pb:\n",
    "                    re += 1\n",
    "            return re\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                re = getdis(words[i],words[j])\n",
    "                dis[i][j] = re\n",
    "                dis[j][i] = re\n",
    "                \n",
    "        @cache\n",
    "        def dp(i):\n",
    "            re = [words[i]]\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if i == n-1:\n",
    "                return re\n",
    "            mlist = []\n",
    "            for j in range(i+1,n):\n",
    "                if dis[i][j] <= 1 and groups[i] != groups[j]:\n",
    "                    mlist.append([j, len(dp(j))])\n",
    "            if len(mlist) == 0:\n",
    "                return re\n",
    "            mm = 0\n",
    "            mi = 0\n",
    "            for mj,ml in mlist:\n",
    "                if ml > mm:\n",
    "                    mm = ml\n",
    "                    mi = mj\n",
    "            print(mi)\n",
    "            return re + dp(mi)\n",
    "        \n",
    "        \n",
    "        \n",
    "        mlist = []\n",
    "        for j in range(0,n):\n",
    "            mlist.append([j, len(dp(j))])\n",
    "        mm = 0\n",
    "        mi = 0\n",
    "        for mj,ml in mlist:\n",
    "            if ml > mm:\n",
    "                mm = ml\n",
    "                mi = mj\n",
    "                \n",
    "        return dp(mi)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def han_dist(s1, s2):\n",
    "            n = len(s1)\n",
    "            if len(s2) != n:\n",
    "                return False\n",
    "            flag = False\n",
    "            for a, b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    if flag:\n",
    "                        return False\n",
    "                    flag = True\n",
    "            return True\n",
    "\n",
    "        mp = [[0] * n for _ in range(n)]\n",
    "        for i, a in enumerate(words):\n",
    "            for j in range(i + 1, n):\n",
    "                b = words[j]\n",
    "                if han_dist(a, b) and groups[i] != groups[j]:\n",
    "                    mp[i][j] = 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            max_idx = -1\n",
    "            for i in range(cur + 1, n):\n",
    "                if mp[cur][i]:\n",
    "                    if max_idx == -1 or len(dfs(i)) > len(dfs(max_idx)):\n",
    "                        max_idx = i\n",
    "            tmp = [] if max_idx == -1 else dfs(max_idx).copy()\n",
    "            tmp.append(words[cur])\n",
    "            return tmp.copy()\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            tmp = dfs(i)\n",
    "            if len(tmp) > len(ans):\n",
    "                ans = tmp.copy()\n",
    "        return list(reversed(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def mm(n, w, g):\n",
    "        a = {}\n",
    "        b = {}\n",
    "        def h(x, y):\n",
    "            if len(x)==len(y):\n",
    "                num = 0\n",
    "                for j in range(len(x)):\n",
    "                    if x[j]!=y[j]:\n",
    "                        num += 1 \n",
    "                if num==1:\n",
    "                    return 1 \n",
    "                return 0\n",
    "            else:\n",
    "                return 0 \n",
    "        for j in range(n):\n",
    "            tmp = set()\n",
    "            t2 = set()\n",
    "            for k in range(j+1, n):\n",
    "                if h(w[j], w[k]):\n",
    "                    tmp.add(k) \n",
    "                if g[j]!=g[k]:\n",
    "                    t2.add(k)\n",
    "            a[j] = tmp \n",
    "            b[j] = t2 \n",
    "\n",
    "        @cache \n",
    "        def f(j):\n",
    "            r1 = a[j]\n",
    "            r2 = b[j] \n",
    "            r3 = r1&r2 \n",
    "            if not r3:\n",
    "                return [1, j] \n",
    "            else:\n",
    "                ans = [-1]\n",
    "                for r in r3:\n",
    "                    tmp = f(r)[::]\n",
    "                    if ans[0]<tmp[0]:\n",
    "                        ans = tmp  \n",
    "                ans.append(j)\n",
    "                ans[0] += 1 \n",
    "                return ans[::] \n",
    "        ans = [f(j) for j in range(n)]\n",
    "        a = max([j[0] for j in ans])\n",
    "        for j in ans:\n",
    "            if j[0]==a:\n",
    "                b = j[1:]\n",
    "                b.sort()\n",
    "                return [w[j] for j in b]\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, w: List[str], g: List[int]) -> List[str]:\n",
    "        return mm(n, w, g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], g: List[int]) -> List[str]:\n",
    "        v=[[0]*n for _ in range(n)]\n",
    "        for i,s in enumerate(words):\n",
    "            for j in range(i,n):\n",
    "                if len(words[j])==len(s) and sum(x!=y for x,y in zip(s,words[j]))==1:v[i][j]=v[j][i]=1\n",
    "        p,f=[-1]*n,[-1]*n\n",
    "        def dfs(i):\n",
    "            if f[i]!=-1:return f[i]\n",
    "            mx=1\n",
    "            for j in range(i+1,n):\n",
    "                if v[i][j] and g[i]!=g[j]:\n",
    "                    a=1+dfs(j)\n",
    "                    if a>mx:mx,p[i]=a,j\n",
    "            f[i]=mx\n",
    "            return mx\n",
    "        a, mx = 0, 0\n",
    "        for i in range(n-1):\n",
    "            if f[i]==-1:dfs(i)\n",
    "            if f[i]>mx:a,mx=i,f[i]\n",
    "        ans=[words[a]]\n",
    "        while p[a]!=-1:ans.append(words[p[a]]);a=p[a]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        visited=defaultdict(list)\n",
    "        dp=[1]*n\n",
    "        visited[words[0]].append(0)\n",
    "        g=Counter()\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            w=words[i]\n",
    "            for j in range(len(w)):\n",
    "                c=w[j]\n",
    "                for k in range(1,26):\n",
    "                    x=chr((ord(c)+k-ord('a'))%26+ord('a'))\n",
    "                    nw=w[:j]+x+w[j+1:]\n",
    "                    #print(nw)\n",
    "                    for u in visited[nw]:\n",
    "                        if groups[u]!=groups[i]:\n",
    "                            if dp[i]<dp[u]+1:\n",
    "                                dp[i]=max(dp[i],dp[u]+1)\n",
    "                                g[i]=u\n",
    "            visited[w].append(i)\n",
    "     #   print(g)\n",
    "     #   print(dp)\n",
    "        mxi,mxv=0,dp[0]\n",
    "        for i,x in enumerate(dp):\n",
    "            if x>mxv:\n",
    "                mxv=x\n",
    "                mxi=i\n",
    "   #     print(mxi)\n",
    "        \n",
    "        i=mxi\n",
    "        ans=[words[i]]\n",
    "        while i in g:\n",
    "            ans.append(words[g[i]])\n",
    "            i=g[i]\n",
    "        return ans[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        nums=[0]*n\n",
    "        mp=defaultdict(bool)\n",
    "        dp=[1]*n\n",
    "        res=[]\n",
    "        t=1\n",
    "        for i in range(10):\n",
    "            for j in range(1,256):\n",
    "                mp[j*t]=True\n",
    "            t=t*256\n",
    "        for i in range(n):\n",
    "            tmp=0\n",
    "            for j in range(len(words[i])):\n",
    "                tmp=tmp*256+ord(words[i][j:j+1])-ord('a')\n",
    "            nums[i]=tmp\n",
    "        maxi=0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if(groups[j]!=groups[i] and len(words[i])==len(words[j]) and mp[nums[i]^nums[j]]):\n",
    "                    dp[i]=max(dp[i],1+dp[j])\n",
    "            if dp[i]>dp[maxi]:\n",
    "                maxi=i\n",
    "        idxs=[maxi]\n",
    "        maxl=dp[maxi]-1\n",
    "        for i in range(maxi-1,-1,-1):\n",
    "            if (groups[i]!=groups[maxi]and len(words[i])==len(words[maxi]) and mp[nums[i]^nums[maxi]]) and dp[i]==maxl:\n",
    "                idxs.append(i)\n",
    "                maxi=i\n",
    "                maxl-=1\n",
    "        \n",
    "        for idx in idxs[::-1]:\n",
    "            res.append(words[idx])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "\n",
    "        @cache\n",
    "        def han(w1, w2):\n",
    "            return len(w1) == len(w2) and sum(x != y for x, y in zip(w1, w2))==1\n",
    "\n",
    "        zuiduo = [1]*n\n",
    "        tiaozhuan = [0]*n\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if zuiduo[j]>=zuiduo[i] and groups[i]!=groups[j] and han(words[i],words[j]):\n",
    "                    zuiduo[i]=zuiduo[j]+1\n",
    "                    tiaozhuan[i]=j\n",
    "\n",
    "        zuida=max(zuiduo)\n",
    "        ans=['']*zuida\n",
    "        qishi=zuiduo.index(zuida)\n",
    "        for i in range(zuida):\n",
    "            ans[i]=words[qishi]\n",
    "            qishi=tiaozhuan[qishi]\n",
    "\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        g = [[] for _ in range(11)]\n",
    "        for s, c in zip(words, groups):\n",
    "            g[len(s)].append((s, c))\n",
    "\n",
    "        @cache\n",
    "        def check(s1: str, s2: str) -> bool:\n",
    "            cnt = 0\n",
    "            for c1, c2 in zip(s1, s2):\n",
    "                if c1 != c2:\n",
    "                    cnt += 1\n",
    "            return cnt == 1\n",
    "        \n",
    "        ans = 0\n",
    "        seq = []\n",
    "        for group in g:\n",
    "            if len(group) == 0:\n",
    "                continue\n",
    "            dp = [1] * len(group)\n",
    "            pre = [-1] * len(group)\n",
    "            for i in range(len(group)):\n",
    "                for j in range(i):\n",
    "                    if check(group[i][0], group[j][0]) and group[i][1] != group[j][1] and dp[i] < dp[j] + 1:\n",
    "                        dp[i] = dp[j] + 1\n",
    "                        pre[i] = j\n",
    "            res = max(dp)\n",
    "            if res > ans:\n",
    "                ans = res\n",
    "                i = dp.index(res)\n",
    "                seq = []\n",
    "                while i >= 0:\n",
    "                    seq.append(group[i][0])\n",
    "                    i = pre[i]\n",
    "        return seq[::-1] if seq else words[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        @cache \n",
    "        def check(i, j):\n",
    "            if len(words[i]) != len(words[j]) or groups[i] == groups[j]:\n",
    "                return False\n",
    "            d = 0  \n",
    "            for k in range(len(words[i])):\n",
    "                if words[i][k] != words[j][k]:\n",
    "                    d += 1 \n",
    "            return d == 1  \n",
    "        dp = [1] * n \n",
    "        dp[0] = 1 \n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if check(j, i):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        mx = max(dp)\n",
    "        res = []\n",
    "        if mx == 1:\n",
    "            res.append(words[-1])\n",
    "        j = n - 1\n",
    "        while len(res) != mx:\n",
    "            if dp[j] == mx:\n",
    "                res.append(words[j])\n",
    "                while dp[j] > 1:\n",
    "                    i = j - 1 \n",
    "                    while i >= 0:\n",
    "                        if check(i, j) and dp[i] + 1 == dp[j]:\n",
    "                            j = i \n",
    "                            res.append(words[j])\n",
    "                            break \n",
    "                        i -= 1\n",
    "                        \n",
    "                break \n",
    "            j -= 1\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        @cache\n",
    "        def check(i, j):\n",
    "            if groups[i] == groups[j]:\n",
    "                return False\n",
    "            s1 = words[i]\n",
    "            s2 = words[j]\n",
    "            if len(s1) != len(s2):\n",
    "                return False\n",
    "            cnt = 0\n",
    "            for a, b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    cnt += 1\n",
    "            if cnt == 1:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        dp = [(1, [i]) for i in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if check(j, i):\n",
    "                    if dp[j][0] + 1 > dp[i][0]:\n",
    "                        arr = dp[j][1][::]\n",
    "                        arr.append(i)\n",
    "                        dp[i] = (dp[j][0] + 1, arr)\n",
    "        maxn = 0\n",
    "        ans = []\n",
    "        \n",
    "        for i in range(n):\n",
    "            if dp[i][0] > maxn:\n",
    "                maxn = dp[i][0]\n",
    "                ans = dp[i][1]\n",
    "        return [words[i] for i in ans[::-1]]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        @cache\n",
    "        def f(i, pword, pg):\n",
    "            if i == n: return []\n",
    "            rnt = f(i+1, pword, pg)\n",
    "            if pg != groups[i] and len(pword) == len(words[i]):\n",
    "                diff = 0\n",
    "                for x, y in zip(words[i], pword):\n",
    "                    if x != y: diff += 1\n",
    "                    if diff > 1: break\n",
    "                if diff == 1: \n",
    "                    rnt2 = [i] + f(i+1, words[i], groups[i])\n",
    "                    if len(rnt2) > len(rnt): return rnt2\n",
    "            return rnt\n",
    "        lst = []\n",
    "        for i in range(n):\n",
    "            lst2 = [i] + f(i+1, words[i], groups[i])\n",
    "            if len(lst2) > len(lst): lst = lst2\n",
    "        ans = []\n",
    "        for i in lst: ans.append(words[i])\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        g = defaultdict(lambda: SortedList())\n",
    "        \n",
    "        for ind, val in enumerate(words):\n",
    "            gv = groups[ind]\n",
    "            \n",
    "            g[val].add([ind, gv])\n",
    "            k = len(val)\n",
    "            \n",
    "\n",
    "        # print(g)\n",
    "        \n",
    "\n",
    "        res = [words[0]]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(ind, pre_group):\n",
    "            nonlocal res\n",
    "            val = words[ind]\n",
    "            k = len(val)\n",
    "            cur = []\n",
    "            \n",
    "            \n",
    "            for i in range(k):\n",
    "                for l in \"abcdefghijklmnopqrstuvwxyz\":\n",
    "                    if l != val[i]:\n",
    "                        pre = val[:i] + l + val[i+1:]\n",
    "                        nxt = bisect.bisect_right(g[pre], [ind,])\n",
    "                        # print(path, val, nxt, g[pre])\n",
    "                        curind = 0\n",
    "                        while curind <= nxt and curind < len(g[pre]):\n",
    "                            if g[pre][curind][1] != pre_group and g[pre][curind][0] <= ind:\n",
    "                                nxt_path = dfs(g[pre][curind][0], g[pre][curind][1])\n",
    "                                if len(nxt_path) > len(cur):\n",
    "                                    cur = nxt_path\n",
    "                            curind += 1\n",
    "            \n",
    "            return [val] + cur\n",
    "        \n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            ans = dfs(i, groups[i])\n",
    "            if len(ans) > len(res): res = ans\n",
    "        return res[::-1]\n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def getC(s1, s2):\n",
    "            if len(s1) != len(s2): return inf\n",
    "            count = 0\n",
    "            for index in range(len(s1)):\n",
    "                if s1[index] != s2[index]:\n",
    "                    count += 1\n",
    "                if count > 1: return inf\n",
    "            return inf if not count else 1\n",
    "        \n",
    "        @cache \n",
    "        def dp(i, preI):\n",
    "            if i < 0: return ''\n",
    "\n",
    "            r2 = dp(i - 1, preI)\n",
    "            if (i == preI or groups[i] != groups[preI]) and (i == preI or getC(words[i], words[preI]) == 1):\n",
    "                r1 = list(dp(i - 1, i)) + [words[i]]\n",
    "                return r1 if len(r1) > len(r2) else r2\n",
    "            return r2\n",
    "\n",
    "        res = []\n",
    "        for index in range(n):\n",
    "            t = dp(index, index)\n",
    "            if len(t) > len(res):\n",
    "                res = t\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # @cache\n",
    "        def getC(s1, s2):\n",
    "            if len(s1) != len(s2): return inf\n",
    "            if s1 == s2: return inf\n",
    "            count = 0\n",
    "            for index in range(len(s1)):\n",
    "                if s1[index] != s2[index]:\n",
    "                    count += 1\n",
    "                if count > 1: return inf\n",
    "            return 1\n",
    "        \n",
    "        @cache \n",
    "        def dp(i, preI):\n",
    "            if i < 0: return ''\n",
    "\n",
    "            r2 = dp(i - 1, preI)\n",
    "            if (i == preI or groups[i] != groups[preI]) and (i == preI or getC(words[i], words[preI]) == 1):\n",
    "                r1 = list(dp(i - 1, i)) + [words[i]]\n",
    "                return r1 if len(r1) > len(r2) else r2\n",
    "            return r2\n",
    "\n",
    "        res = []\n",
    "        for index in range(n):\n",
    "            t = dp(index, index)\n",
    "            if len(t) > len(res):\n",
    "                res = t\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        @cache\n",
    "        def hanmin(i:int, j:int) -> int:\n",
    "            if len(words[i]) != len(words[j]):\n",
    "                return -1\n",
    "            cnt = 0\n",
    "            for x, y in zip(words[i], words[j]):\n",
    "                cnt += x != y\n",
    "            return cnt\n",
    "        \n",
    "        @cache\n",
    "        def dp(i:int) -> int:\n",
    "            if i == n:\n",
    "                return []\n",
    "            subs = [dp(j).copy() for j in range(i + 1, n) if groups[j] != groups[i] and hanmin(i, j) == 1]\n",
    "            sub = max(subs, key = lambda x: len(x)) if subs else[]\n",
    "            return [words[i]] + sub\n",
    "        \n",
    "\n",
    "        return max([dp(i) for i in range(n)], key = lambda x: len(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        # hamming_distances = [[0] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         hamming_distances[i][j] = sum(ch1 != ch2 for ch1, ch2 in zip(words[i], words[j]))\n",
    "                \n",
    "        # 2. Sort and/or group by length and groups value\n",
    "        # sorted_indices = sorted(range(n), key=lambda i: (len(words[i]), groups[i]))\n",
    "        def hamming_distance(ch1, ch2):\n",
    "            ans = 0\n",
    "            for c1, c2 in zip(ch1, ch2):\n",
    "                if c1 != c2:\n",
    "                    ans += 1\n",
    "            return ans\n",
    "        \n",
    "        \n",
    "        @cache\n",
    "        def dfs(prev_idx, cur_idx):\n",
    "            # Base case\n",
    "            if cur_idx >= n:\n",
    "                return []\n",
    "            \n",
    "            # Check if words[prev_idx] and words[cur_idx] can be consecutive in a valid subsequence\n",
    "            if prev_idx is not None and (\n",
    "                    groups[prev_idx] == groups[cur_idx] or\n",
    "                    len(words[prev_idx]) != len(words[cur_idx]) or\n",
    "                    hamming_distance(words[prev_idx], words[cur_idx]) != 1\n",
    "            ):\n",
    "                return []\n",
    "            \n",
    "            # Check the rest of the sequence and get the best solution\n",
    "            best_subseq = []\n",
    "            for next_idx in range(cur_idx + 1, n):\n",
    "                if groups[cur_idx] != groups[next_idx]:\n",
    "                    subseq = dfs(cur_idx, next_idx)\n",
    "                    if len(subseq) > len(best_subseq):\n",
    "                        best_subseq = subseq\n",
    "            \n",
    "            return [words[cur_idx]] + best_subseq\n",
    "        \n",
    "        # Run the DFS and get the longest subsequence\n",
    "        return max((dfs(None, i) for i in range(n)), key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        def x(lw, rw):\n",
    "            if rw == '':\n",
    "                return True\n",
    "            return len(lw) == len(rw) and sum(int(l != r) for l, r in zip(lw, rw)) == 1\n",
    "        y = lambda s: sum(len(i) for i in s)\n",
    "        @lru_cache(None)\n",
    "        def f(i, lw='', lg=-1):\n",
    "            if i == n:\n",
    "                return []\n",
    "            if groups[i] != lg and x(words[i], lw):\n",
    "                return max([words[i]] + f(i + 1, words[i], groups[i]), f(i + 1, lw, lg), key=len)\n",
    "            else:\n",
    "                return f(i + 1, lw, lg)\n",
    "        return f(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getWordsInLongestSubsequence(self, n: int, words: List[str], groups: List[int]) -> List[str]:\n",
    "        dic = defaultdict(list)\n",
    "        s = string.ascii_lowercase\n",
    "        for w, g in zip(words, groups):\n",
    "            dic[len(w)].append((w, g))\n",
    "            \n",
    "            \n",
    "        def cal(A):\n",
    "            dic1 = defaultdict(set)\n",
    "            dic2 = defaultdict(set)\n",
    "            pre = defaultdict(set)\n",
    "            for i, (w, g) in enumerate(A):\n",
    "                for j, c in enumerate(w):\n",
    "                    for x in s:\n",
    "                        if x == c: continue\n",
    "                        tmp = w[: j] + x + w[j + 1:]\n",
    "                        pre[i] |= (dic1[tmp] - dic2[tmp, g])\n",
    "                dic1[w].add(i)\n",
    "                dic2[w, g].add(i)\n",
    "            B = [[] for _ in range(len(A))]\n",
    "            for i, (w, g) in enumerate(A):\n",
    "                cur = [w]\n",
    "                for j in pre[i]:\n",
    "                    if len(B[j]) + 1 > len(cur):\n",
    "                        cur = B[j] + [w]\n",
    "                B[i] = cur\n",
    "            return max(B, key=len)\n",
    "                \n",
    "                        \n",
    "        ans = []\n",
    "        for v in dic.values():\n",
    "            cur = cal(v)\n",
    "            if len(cur) > len(ans):\n",
    "                ans = cur\n",
    "        return ans        \n",
    "            \n",
    "            \n",
    "        \n",
    "#         def cal(A):\n",
    "#             B = SortedList()\n",
    "#             dic1 = {}\n",
    "#             dic2 = {}\n",
    "#             for w, g in A:\n",
    "#                 cur = [w]\n",
    "#                 if B:\n",
    "#                     if B[-1][1] != g:\n",
    "#                         if B[-1][0] + 1 > len(cur):\n",
    "#                             cur = dic2[B[-1][1]] + [w]\n",
    "#                     else:\n",
    "#                         if len(B) > 1:\n",
    "#                             if B[-2][0] + 1 > len(cur):\n",
    "#                                 cur = dic2[B[-2][1]] + [w]\n",
    "#                 if g not in dic1:\n",
    "#                     dic1[g] = len(cur)\n",
    "#                     dic2[g] = cur\n",
    "#                     B.add((len(cur), g))\n",
    "#                 elif len(cur) > dic1[g]:\n",
    "#                     B.remove((dic1[g], g))\n",
    "#                     dic1[g] = len(cur)\n",
    "#                     dic2[g] = cur\n",
    "#                     B.add((dic1[g], g))\n",
    "#             return max(dic2.values(), key=len)\n",
    "        \n",
    "#         ans = []\n",
    "#         for v in dic.values():\n",
    "#             cur = cal(v)\n",
    "#             if len(cur) > len(ans):\n",
    "#                 ans = cur\n",
    "#         return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
